#-*- coding:utf-8 -*-

import math
import numpy as np
import pylab as pl

 #数据集：每三个是一组分别是西瓜的编号，密度，含糖量
data = """
1.390489288 
1.58332632	
1.421662408	
4.463208766	
2.791373323	
1.118085215	
1.572610092	
2.333261066	
1.765203539	
2.003671966	
2.294879261	
2.45366102	
0.884648606	
1.706087077	
1.083298739	
2.569547021	
2.180953061	
0.511461133	
1.343684789	
3.197216148	
2.823076249	
1.023619271	
2.180171257	
2.466982922	
2.468095282	
2.261678198	
1.193838019	
1.544090372	
3.040607685	
1.338093605	
2.30432904	
1.325313219	
1.74451952	
1.630703153	
1.244163706	
0.499511809	
2.46163307	
1.960607818	
1.575913207	
2.284358312	
2.576258355	
2.221614706	
1.196500147	
1.1610642	
2.363267784	
1.728417456	
1.174998442	
3.664585709	
2.213725008	
2.084375397	
1.824757358	
1.158024645	
2.036176113	
2.390140194	
2.055683819	
2.720145366	
1.676511188	
2.243882594	
1.285138308	
2.053591389	
2.550111563	
1.565927147	
3.886142863	
1.669583036	
2.672741758	
2.804131693	
2.165996776	
2.879718631	
1.939687881	
2.685834149	
1.307112157	
1.278460106	
2.229048068	
0.684280258	
2.481063397	
0.934780535	
2.598283684	
1.733493252	
1.450439684	
2.288286437	
1.410496168	
3.896441924	
5.299445533	
4.4293104	
5.343550655	
4.452260266	
4.614247664	
5.375815659	
5.427714189	
5.763967479	
4.226221709	
6.077115689	
4.832781758	
3.675113194	
5.519542688	
4.46853849	
5.064298702	
5.457827366	
6.117715433	
4.439239021	
5.592440896	
5.613314886	
6.715906711	
4.713009718	
5.061583844	
5.151422928	
5.047335704	
4.52429533	
3.920132986	
4.350163541	
5.194945176	
4.31760788	
3.462327771	
5.802293612	
4.838572057	
6.092490026	
5.892873116	
4.818493769	
5.677879515	
5.894206042	
4.954725736	
5.279200328	
5.557182632	
5.493428162	
5.122508503	
4.13451611	
3.991605148	
4.892981431	
6.549784953	
3.5733247	
4.926037604	
4.682672766	
4.886922623	
4.308901205	
4.067426124	
4.687976753	
5.853693287	
4.975959625	
4.155426907	
5.662036716	
4.880410352	
5.596104365	
5.137966851	
4.895718642	
4.74870877	
5.190447801	
4.849920397	
3.952564428	
2.880205644	
4.316193698	
5.696393031	
4.696101374	
4.834144121	
3.953784981	
5.539851077	
5.46186194	
4.391326006	
5.298866185	
5.39946721	
4.184332347	
4.59979332	
3.926431428	
5.120790228	
6.04259564	
5.443682691	
5.63083921	
5.566125308	
4.912725197	
7.17938437	
6.601238372	
5.146163781	
4.635833897	
4.891234829	
5.600878327	
3.727465502	
4.343871322	
4.888255072	
4.846280415	
4.193713683	
3.551359697	
5.458354413	
5.345915999	
9.218623713	
7.152725345	
8.059519722	
9.786872612	
8.117017795	
8.628293606	
7.846229366	
8.129871271	
8.913247991	
6.874901479	
6.790482181	
8.400608088	
9.352052265	
7.378759734	
5.476579451	
6.092028262	
9.109386165	
7.534558457	
9.97419756	
7.448416203	
6.621789065	
8.909047053	
6.116601525	
6.937015985	
8.969252798	
7.798597541	
10.01043338	
6.339376796	
6.838536582	
8.709317839	
8.290235577	
9.352461193	
8.009295877	
7.161681591	
7.718581702	
9.387831773	
10.28183125	
9.311955848	
8.785335036	
7.539759461	
9.079483351	
8.516343324	
7.170957474	
7.670831427	
9.169661946	
7.397942082	
7.234220011	
9.18221318	
7.868937164	
8.582392321	
5.985501429	
8.956680821	
7.845006027	
8.364290556	
9.340912577	
7.840189014	
8.148007831	
7.155269064	
8.354661233	
6.345032528	
8.065798613	
9.535157028	
7.71441262	
7.428536477	
7.532812146	
9.990325904	
7.291663693	
7.837059942	
10.49845339	
7.211540888	
7.531739005	
10.01212041	
8.693274229	
8.939286267	
8.174132536	
8.824884629	
8.456283577	
7.510259378	
10.91914352	
9.163999256	
9.954434188	
4.96780701	
8.629434558	
10.4138103	
8.61110549	
6.095372226	
8.164852745	
8.532937347	
7.298474297	
7.129758747	
5.842209117	
7.228674373	
6.151751411	
6.148695685	
7.856123742	
8.608780068	
6.580310833	
9.786614873	
7.782919755	
8.192536579
2.056951167 	
1.745577498 
1.805092221 
4.351197333 
2.543207698 
1.59663076 
2.369357722 
2.074847808 
1.36116459 
2.786013149 
2.124912183 
2.403129468 
2.012954303 
0.596521187 
1.779278923 
1.841787962 
1.380394114 
2.064802562 
2.809087052 
1.743529729 
2.658017138 
1.976984141 
2.360866229 
2.465333004 
1.784319994 
0.445500218 
2.829356279 
2.226015738 
1.386652819 
1.66002368 
1.858712669 
0.914666855 
1.847409628 
1.819239201 
2.378971108 
2.09978411 
1.41430788 
2.201332522 
1.9905862 
1.353366779 
2.755231538 
2.010427859 
2.341440116 
3.097643704
2.182724828
0.498346074
2.252076591
2.510770582
1.626028844
2.66397274
3.305311633
1.740396371
0.651785747
2.053678179
2.548348389
2.553507407
1.967851262
1.132807611
1.705395745
3.235741879
1.694674489
3.058319427
2.115532963
1.025268821
2.199906099
1.372993125
1.548708029
1.619678478
1.76000398
2.295620959
1.563445365
2.348937837
0.871565359
1.972124882
2.116473777
0.929256348
1.899692637
2.908180838
2.093454547
2.565716956
2.246549826
0.956045874
4.841460264
4.425931995
6.597782011
5.373262103
6.36383058
4.904845165
4.996147879
4.871942825
5.170050166
4.174331017
5.693331433
5.431557588
5.147303742
4.99507709
5.645323333
4.75833946
4.964925163
4.697490245
5.134698995
5.047763057
3.850706249
4.941885022
6.004741568
4.920734696
5.518531451
5.311061373
4.945630813
4.549525561
4.22369546
3.954057455
4.895450042
4.874463963
4.277753492
4.827904739
5.249766295
5.746679672
4.923103665
6.229093565
4.823580203
5.24271216
4.82364256
5.723532146
5.105775403
4.190767408
4.141441289
3.885709469
5.510103981
4.203360099
3.81811343
5.752790071
4.953604076
4.616593601
5.251305813
5.540522519
5.743266745
4.65224874
5.081771267
4.764757997
5.42524735
4.022329225
5.135120528
5.616021072
4.429929805
5.317260138
5.549324848
4.258307248
5.35977096
4.825343241
5.035198317
4.414556106
5.416021311
4.952839533
4.019699113
5.47143328
3.961888959
5.557696442
5.526365897
5.402854906
4.612656639
5.759143835
5.692491804
4.215305069
4.99119557
5.764309257
4.435847836
5.182258605
5.846365888
5.286003524
5.423085155
5.856704863
4.052214769
3.917712022
5.199002769
4.371594855
4.662657782
5.187725883
4.155278328
4.730732585
4.515437835
5.372816485
9.216935084
6.946089744
7.182230314
9.697210275
7.474633711
7.192783442
7.347525959
9.387871
9.40663188
8.221156056
8.473339142
9.594461753
8.80346435
7.414527617
7.448585418
9.143685708
8.170093562
8.175969037
9.659412747
8.207145925
8.492899016
9.107054987
8.620683568
7.536837409
8.366792939
8.746281031
7.233102719
6.570443596
7.174410544
5.434502792
7.042541739
6.947655916
6.846769504
7.680028501
7.354480017
8.676671277
7.658922483
5.417936213
8.456902512
8.855278441
9.271334948
8.73931515
6.652930498
8.229456957
7.027661954
11.65860286
10.36197268
7.313902108
7.735351667
9.679738379
10.4891865
7.324850634
8.368483901
9.476962989
7.558795033
8.902497154
9.39768748
8.580169922
9.711981447
8.00091931
5.119456611
11.45535518
8.353049541
8.472710865
7.87481278
6.957907244
7.906626852
9.770350889
6.79681202
8.640185074
10.45120789
8.687593236
7.583772156
9.386754086
10.37160495
7.864563178
9.348811473
7.894881062
7.417077145
9.006338738
8.646994757
6.951390631
8.317063141
9.729767338
8.101881592
10.29168635
6.098416834
8.126633691
8.606466453
6.341929206
7.552514986
8.541384811
7.743870403
10.22598121
9.508237052
9.117571671
9.546793286
5.445521873
7.197938904
6.954222273"""

#数据处理 dataset是30个样本（密度，含糖量）的列表
a = data.split('\n')
dataset = [(float(a[i]), float(a[i+1])) for i in range(1, len(a)-1, 3)]

#计算欧几里得距离,a,b分别为两个元组
def dist(a, b):
    return math.sqrt(math.pow(a[0]-b[0], 2)+math.pow(a[1]-b[1], 2))

#算法模型
def DBSCAN(D, e, Minpts):
    #初始化核心对象集合T,聚类个数k,聚类集合C, 未访问集合P,
    T = set(); k = 0; C = []; P = set(D)
    for d in D:
        if len([ i for i in D if dist(d, i) <= e]) >= Minpts:
            T.add(d)
    #开始聚类
    while len(T):
        P_old = P
        o = list(T)[np.random.randint(0, len(T))]
        P = P - set(o)
        Q = []; Q.append(o)
        while len(Q):
            q = Q[0]
            Nq = [i for i in D if dist(q, i) <= e]
            if len(Nq) >= Minpts:
                S = P & set(Nq)
                Q += (list(S))
                P = P - S
            Q.remove(q)
        k += 1
        Ck = list(P_old - P)
        T = T - set(Ck)
        C.append(Ck)
    return C

#画图
def draw(C):
    colValue = ['r', 'y', 'g', 'b', 'c', 'k', 'm']
    for i in range(len(C)):
        coo_X = []    #x坐标列表
        coo_Y = []    #y坐标列表
        for j in range(len(C[i])):
            coo_X.append(C[i][j][0])
            coo_Y.append(C[i][j][1])
        pl.scatter(coo_X, coo_Y, marker='x', color=colValue[i%len(colValue)], label=i)

    pl.legend(loc='upper right')
    pl.show()




C = DBSCAN(dataset, 0.4,2.5)
draw(C)